#include <iostream>
#include <vector>
#include <map>
#include <queue>
#include <cstring>

struct P
{
    P() {}
    P(int xi, int yi): x(xi), y(yi) {}
    int8_t x, y;
};

// ---- 参数 ----
// 注： (mapWidth * mapHeight) ^ lenTokens 不应超过 2 ^ 64 ，且不应存在全零状态
// Token形状
const std::vector<P> tokens[] = {
    {{0, 0}, {1, 0}, {0, 1}, {1, 1}}, // 0 曹操
    {{0, 0}, {1, 0}}, // 1 关羽
    {{0, 0}, {0, 1}}, // 2
    {{0, 0}, {0, 1}}, // 3
    {{0, 0}, {0, 1}}, // 4
    {{0, 0}, {0, 1}}, // 5
    {{0, 0}}, // 6
    {{0, 0}}, // 7
    {{0, 0}}, // 8
    {{0, 0}}, // 9
};
const int lenTokens = sizeof(tokens) / sizeof(tokens[0]);
// 地图大小
const int mapWidth = 4, mapHeight = 5;
// 初始状态
const P startState[] = {
    {1, 0}, // 0 曹操位置
    {1, 2}, // 1 关羽位置
    {0, 0}, // 2
    {3, 0}, // 3
    {0, 2}, // 4
    {3, 2}, // 5
    {1, 3}, // 6
    {2, 3}, // 7
    {1, 4}, // 8
    {2, 4}, // 9
};
// 结束条件
bool endCondition(const P state[])
{
    return state[0].x == 1 && state[0].y == 3;
}
// ---- 参数 ----

struct M
{
    int8_t* pMap; // -1为空，-2为边界外，其余为id

    int8_t get(int x, int y)
    {
        if (x < 0 || x >= mapWidth || y < 0 || y >= mapHeight) return -2;
        return pMap[y * mapWidth + x];
    }

    void place(const std::vector<P>& token, int x, int y, int8_t id)
    {
        for (auto it = token.begin(); it != token.end(); it++)
        {
            pMap[(y + it->y) * mapWidth + (x + it->x)] = id;
        }
    }

    void remove(const std::vector<P>& token, int x, int y)
    {
        for (auto it = token.begin(); it != token.end(); it++)
        {
            pMap[(y + it->y) * mapWidth + (x + it->x)] = -1;
        }
    }

    bool canPlace(const std::vector<P>& token, int x, int y, int8_t id)
    {
        for (auto it = token.begin(); it != token.end(); it++)
        {
            int8_t mapId = get(x + it->x, y + it->y);
            if (mapId != -1 && mapId != id) return false;
        }
        return true;
    }

    void clear()
    {
        memset(pMap, -1, sizeof(uint8_t) * mapWidth * mapHeight);
    }

    M clone()
    {
        int8_t* newPMap = new int8_t[mapWidth * mapHeight];
        memcpy(newPMap, pMap, sizeof(uint8_t) * mapWidth * mapHeight);
        return { newPMap };
    }

    void print()
    {
        for (int y = 0; y < mapHeight; y++)
        {
            for (int x = 0; x < mapWidth; x++)
            {
                int8_t mapId = get(x, y);
                if (mapId == -1) std::cout << '_';
                else std::cout << (int)mapId;
                std::cout << ' ';
            }
            std::cout << std::endl;
        }
        std::cout << std::endl;
    }
};

struct QObj
{
    uint64_t hState;
    uint64_t prevHState;
    M map;
};

uint64_t zip(const P state[])
{
    const int base = mapWidth * mapHeight;
    uint64_t mul = 1;
    uint64_t hash = 0;
    for (int i = 0; i < lenTokens; i++)
    {
        hash += (state[i].y * mapWidth + state[i].x) * mul;
        mul *= base;
    }
    return hash;
}

void unzip(uint64_t hash, P state[])
{
    const int base = mapWidth * mapHeight;
    for (int i = 0; i < lenTokens; i++)
    {
        int n = hash % base;
        state[i] = P(n % mapWidth, n / mapWidth);
        hash /= base;
    }
}

const P directions[] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
const int lenDirections = sizeof(directions) / sizeof(directions[0]);

std::map<uint64_t, uint64_t> visited;
uint64_t visitedCount = 0;

std::queue<QObj> queue;

P state[lenTokens];

int main()
{
    uint64_t startHState = zip(startState);

    M startMap = { new int8_t[mapWidth * mapHeight] };
    startMap.clear();
    for (int id = 0; id < lenTokens; id++)
    {
        startMap.place(tokens[id], startState[id].x, startState[id].y, id);
    }
    startMap.print();

    queue.push({ startHState, 0, startMap });

    while (1)
    {
        // 队列空，无解
        if (queue.empty())
        {
            std::cout << "No solution!" << std::endl;
            break;
        }

        QObj obj = queue.front();
        queue.pop();
        unzip(obj.hState, state);

        // 已访问
        if (visited.find(obj.hState) != visited.end())
        {
            delete[] obj.map.pMap;
            continue;
        }

        // 结束
        if (endCondition(state))
        {
            std::cout << "Done! (" << visitedCount << " states visited)" << std::endl;
            std::vector<uint64_t> steps = { obj.hState };
            uint64_t hState = obj.prevHState;
            while (hState)
            {
                steps.push_back(hState);
                hState = visited[hState];
            }
            std::cout << "Taking " << steps.size() << " steps" << std::endl;
            for (int i = steps.size() - 1; i >= 0; i--)
            {
                unzip(steps[i], state);
                obj.map.clear();
                for (int id = 0; id < lenTokens; id++)
                {
                    obj.map.place(tokens[id], state[id].x, state[id].y, id);
                }
                obj.map.print();
            }
            delete[] obj.map.pMap;
            break;
        }

        visited[obj.hState] = obj.prevHState;
        visitedCount++;
        if (visitedCount % 100000 == 0)
        {
            std::cout << visitedCount << " states visited" << std::endl;
        }

        for (int id = 0; id < lenTokens; id++)
        {
            int x = state[id].x, y = state[id].y;
            for (int di = 0; di < lenDirections; di++)
            {
                int nx = x + directions[di].x, ny = y + directions[di].y;
                if (obj.map.canPlace(tokens[id], nx, ny, id))
                {
                    state[id] = P(nx, ny);
                    uint64_t newHState = zip(state);
                    if (newHState == obj.hState) continue;

                    M newMap = obj.map.clone();
                    newMap.remove(tokens[id], x, y);
                    newMap.place(tokens[id], nx, ny, id);

                    queue.push({ newHState, obj.hState, newMap });
                }
            }
            state[id] = P(x, y);
        }

        delete[] obj.map.pMap;
    }

    while (!queue.empty())
    {
        delete[] queue.front().map.pMap;
        queue.pop();
    }

    return 0;
}
